/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    void _Convert(TreeNode* root, TreeNode*& parent)
    {
        if (root == nullptr)
            return;
        _Convert(root->left, parent);
        root->left = parent;
        if (parent)
            parent->right = root;
        parent = root;
        _Convert(root->right, parent);
    }

    TreeNode* Convert(TreeNode* pRootOfTree) {
        if (pRootOfTree == nullptr)
            return pRootOfTree;
        TreeNode* parent = nullptr;
        _Convert(pRootOfTree, parent);
        while (pRootOfTree->left)
            pRootOfTree = pRootOfTree->left;
        return pRootOfTree;
    }

};